#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
//首先要将二叉树结点的数据结构定义清楚
typedef struct node {
	char c;  //结点内存的元素类型
	struct node* left;  //指向左子结点的指针
	struct node* right;  //指向右子结点的指针
}Node, * pNode;

typedef struct queue_t {
	pNode insertPos;//特别容易错
	struct queue_t* pNext;
}Queue_t, * pQueue_t; //辅助队列数据结构，辅助队列中每个元素放的是树中元素结点的
//地址值，这样才能快速确定树中的结点


#define N 10

void printOder(pNode tree)
{
	if(tree)
	{
		printf("%-3c",tree->c);
		printOder(tree->left);
		printOder(tree->right);
	}
}

void buildBinaryTree(pNode *tree, pQueue_t *queHead, pQueue_t *queTail,char c)
{
	//给树结点申请空间
	pNode pnew=(pNode)calloc(1, sizeof(Node));
	pnew->c = c;
	//给队列结点申请空间
	pQueue_t queNew=(pQueue_t)calloc(1, sizeof(Queue_t));
	queNew->insertPos = pnew;
	pQueue_t temp;
	if (NULL == *tree)
	{
		*tree = pnew;
		*queHead = queNew;
		*queTail = queNew;
	}
	else {
		//先入队
		(*queTail)->pNext = queNew;
		*queTail = queNew;
		if (NULL == (*queHead)->insertPos->left)
		{
			(*queHead)->insertPos->left = pnew;//左边为空，就放左边
		}
		else {
			(*queHead)->insertPos->right = pnew;//右边有空，就放右边
			//出队
			temp = *queHead;
			*queHead = (*queHead)->pNext;//出队
			free(temp);
		}
	}
}

int main()
{
	pNode tree = NULL;
	pQueue_t queHead = NULL, queTail = NULL;
	char c;
	//注意不要输空格
	while(scanf("%c",&c)!=EOF)
	{
		if (c == '\n')
		{
			break;
		}
		buildBinaryTree(&tree, &queHead,&queTail, c);
	}
	puts("前序遍历");
	printOder(tree);
	printf("\n");
	return 0;
}